1. Field of the Invention
This invention relates to magnification or "zoom" processing, particularly reduction processing, of a digital binary image, and to an image processing apparatus and method for obtaining a high-quality zoomed image using contour information.
2. Description of the Related Art
The applicant has already filed applications for such an apparatus disclosed publicly as Japanese Patent Application Laid-Open (KOKAI) No. 5-174140 (prior art 1) and Japanese Patent Application Laid-Open (KOKAI) No. 6-12490 (prior art 2).
According to each of these applications, a binary image per se is not varied in power, or zoomed, when it is desired to output the binary image upon changing its magnification. Rather, contour information of the binary image is extracted and a zoomed image is produced based upon the contour information extracted, whereby it is possible to obtain a high-quality image.
More specifically, Japanese Patent Application Laid-Open No. 5-174140 (prior art 1) teaches to extract an outline vector from a binary image, create a smoothly zoomed outline vector at a desired rate of magnification (arbitrary) in the state of the extracted outline vector representation, and reproduce a binary image from the smoothly zoomed outline vector. In this manner it is attempted to obtain a high-quality digital binary image varied in power at the desired rate of magnification (arbitrary).
The principal elements of this arrangement will be described in general terms. FIG. 9 is a diagram which best illustrates the features of Japanese Patent Application Laid-Open No. 5-174140.
As shown in FIG. 9, a binary image acquisition unit 1 acquires a digital binary image that is to undergo zoom processing and outputs the binary image in a raster-scan format. An outline extraction unit 2 extracts a coarse contour vector (an outline vector prior to smoothing and zoom processing) from the binary image having the raster-scan format. An outline smoothing/zooming unit 3 smoothes and applies zoom processing to the coarse contour vector data in the form of vector data. A binary image reproduction unit 4 reproduces the binary image data in the raster-scan format from the outline vector data. A binary image output unit 5 displays the binary image data in the raster-scan format, produces a hard copy of the data or outputs the data to a communication line or the like.
The binary image acquisition unit 1 is a well-known raster-scanning type binary image output unit which reads the image of an original as a binary image and outputs the image in a raster-scan format. The outline extraction unit 2 is the apparatus described in the specification of Japanese Patent Application Laid-Open (KOKAI) No. 4-157578 already proposed by the applicant.
FIG. 10 illustrates the scanning of the raster-scan binary image data outputted by the binary image acquisition unit 1 as well as the scanning of the raster-scan binary image data which enters the outline extraction unit 2. The raster-scan binary image data outputted by the binary image acquisition unit 1 enters the outline extraction unit 2. In FIG. 10, numeral 101 denotes a pixel in the binary image undergoing raster scanning, and numeral 102 represents a nine-pixel area, namely the pixel 101 and the eight pixels neighboring it. The apparatus constituting the outline extraction unit described in the specification of Japanese Patent Application Laid-Open No. 4-157578 mentioned above shifts a pixel of interest in the order in which raster scanning is performed and, with regard to each pixel of interest, detects contour edge vectors (horizontal or vertical vectors) between the pixel of interest and the pixels neighboring the pixel of interest. If a contour edge vector exists, the apparatus extracts the coordinates of the starting point of this edge vector as well as the data indicating the direction of the vector and extracts the coarse contour vector while updating the connection relationship between edge vectors.
FIG. 11 illustrates an example of extraction of contour edge vectors between a pixel of interest and the pixels neighboring it. In FIG. 11, the ".DELTA." mark indicates the starting point of a vertical vector and the ".omicron." mark the starting point of a horizontal vector.
FIG. 12 depicts an example of coarse-contour vector loops extracted by the outline extraction means described above. Here each box delimited by the grid indicates a pixel position in an input image; blank boxes signify white pixels and the shaded circle marks signify black pixels. As in FIG. 11, the ".DELTA." mark indicates the starting point of a vertical vector and the ".omicron." mark the starting point of a horizontal vector.
It will be appreciated from the example of FIG. 12 that the outline extraction unit 2 extracts areas of contiguous black pixels as coarse-contour vector loops in which a horizontal vector and a vertical vector are always interconnected in alternating fashion. It is so arranged that the direction in which extraction processing advances is such that the side to the right of the direction of advance is the area of the black pixels. Further, the starting point of a coarse-contour vector is extracted as a position intermediate each pixel of the input image. In other words, if the present position of each pixel is represented by integers (x,y), then the starting point of an extracted vector is a value obtained by adding 0.5 to or subtracting 0.5 from each of these coordinates. More specifically, a line segment having a width of one pixel in an original image also is extracted as a coarse contour loop having a significant width. A group of coarse-contour vector loops thus extracted is outputted by the outline extraction unit 2 of FIG. 9 in a data format of the kind shown in FIG. 13. That is, the data comprises the total number N of contours extracted from the image and a group of coarse-contour loop data from a first contour loop to an N-th contour loop. Each item of coarse-contour loop data is composed of the total number of starting points of contour edge vectors present in a coarse-contour loop (this number can be thought of as the total number of contour edge vectors), and a column of values of starting-point coordinates (x- and y-coordinate values) of each contour edge vector in the order in which the edge vectors construct the loop (the starting point of a horizontal vector and the starting point of a vertical vector are arranged in alternating fashion).
Next, the outline smoothing/zoom unit 3 shown in FIG. 9 accepts the coarse-contour vector data (see FIG. 13) from the outline extraction unit 2 as an input and executes smoothing and zoom processing, which is for zooming to a desired magnification, in the form of the outline vector data (coordinate values). FIG. 14 illustrates the construction of the outline smoothing/zoom unit 3 in greater detail. As shown in FIG. 14, the outline smoothing/zoom unit 3 includes a magnification setting device 310 for zooming, and a first smoothing/zooming device 320. The first smoothing/zooming device 320 subjects the entered coarse contour data to smoothing and zoom processing at the magnification set by the magnification setting device 310. The results of processing are smoothed in a second smoothing device 330, whereby a final output is obtained.
The magnification setting device 310, which provides information indicating what the magnification of an input image size should be independently in the main-scan (horizontal) direction and sub-scan (vertical) direction, may deliver values, which have been set in advance by a DIP switch or dial switch, to the first smoothing/zoom device 320, or may have a configuration which supplies the values from some external unit via an interface.
The first smoothing/zoom device 320 obtains the magnification information from the magnification setting device 310 and applies smoothing and zoom processing.
FIG. 15 illustrates an example of hardware for implementing the outline smoothing/zoom unit 3. Shown in FIG. 15 are a CPU 71, a disk unit 72, a disk I/O (interface) 73, a ROM 74 storing the operational processing procedure of the CPU 71, an I/O port 75, a RAM (random-access memory ) 76 and a bus 77 interconnecting these blocks.
The output of the outline extraction unit 2 in FIG. 9 is stored as a file (coarse-contour vector data) in the disk 72 in the form shown in FIG. 13. The CPU 71 operates according to the procedure shown in FIG. 16 and executes outline smoothing/zoom processing.
First, as shown at step S1 in FIG. 16, the CPU 71 reads out the coarse contour data, which has been stored on the disk device 72, via the disk I/O 73 and reads this data into a working area (not shown) in the RAM 76. The CPU 71 then executes first smoothing and zoom processing at step S2.
The first smoothing processing is performed in units of individual closed loops of coarse contour data. The CPU 71 successively targets each contour edge (a horizontal or vertical vector) of each item of coarse contour data, divides the data into a pattern depending upon a combination of lengths and directions of interconnected edge vectors of up to three vectors before and three after each targeted contour edge vector (i.e., three vectors before the targeted edge, the vector of the targeted edge itself and three vectors after the targeted edge, for a total of seven edge vectors), and, with regard to each particular case, defines contour points that have undergone first smoothing, namely contour points that are the result of first smoothing with respect to the targeted edge. The CPU 71 outputs coordinate values of the contour points and additional information (hereinafter referred to as "corner-point information") indicating whether a contour point is a corner point. The corner point mentioned here refers to a point situated at a meaningful corner. Corner points at jaggies caused by noise or the like and corner points resulting from notches or the like are excluded. A contour point that has been subjected to first smoothing and judged to be a corner point is treated as a point not to be smoothed, namely as a fixed point at this position, by subsequent second smoothing. A contour point that has been subjected to first smoothing and judged not to be a corner point (hereinafter referred to a "non-corner point") undergoes further smoothing by subsequent second smoothing.
FIG. 17 illustrates the foregoing. More specifically, FIG. 17 shows a targeted coarse-contour edge vector D.sub.i, three edge vectors D.sub.i-1, D.sub.i-2, D.sub.i-3 before the targeted coarse-contour edge vector, and three vectors D.sub.i+1, D.sub.i+2, D.sub.i+3 after the targeted coarse-contour edge vector, as well as a contour point, which has been subjected to first smoothing, defined with respect to the targeted coarse-contour edge vector D.sub.i.
The processing involved in first smoothing is as described above. The data that has undergone first smoothing is stored successively in a prescribed area of the RAM 76. When the processing of step S2 in FIG. 16 is concluded, the CPU 72 executes the second smoothing processing at step S3.
Second smoothing processing involves entering the data that has undergone first smoothing and then processing this data. More specifically, the number of closed loops, the number of contour points per closed loop, a column of coordinate data of contour points that have undergone first smoothing per closed loop, and a column of additional information of contour points that have undergone first smoothing per closed loop are entered and contour-point data that has undergone second smoothing is outputted.
The contour data that has undergone second smoothing is composed of the number of closed loops, a table of the number of contour points per closed loop, and a column of coordinate data of contour loops that have undergone second smoothing per closed loop, as illustrated in FIG. 18.
The essentials of second smoothing will be described with reference to FIG. 19. Second smoothing is executed in units of individual contour loops, as in the manner of first smoothing, and processing proceeds from one contour point to the next within each contour loop.
In a case where a contour point of interest is a corner point, the coordinates per se of the entered contour point are adopted as the contour-point coordinate data, after second smoothing, of this targeted contour point. In other words, the aforesaid coordinate values are not changed in any way.
In a case where the targeted contour point is a non-corner point, coordinate values obtained by a weighted mean of contour-point coordinates before and after and coordinates of the targeted contour point are adopted as the contour-point coordinate values, after second smoothing, of the targeted contour point. That is, if we let P.sub.i (x.sub.i,y.sub.i) represent a targeted input contour point that is a non-corner point, let P.sub.i-1 (x.sub.i-1,y.sub.i-1) represent the contour point immediately preceding the point P.sub.i on the input contour loop, let P.sub.i+1 (x.sub.i+1,y.sub.i+1) represent the contour point immediately following the point P.sub.i, and let Q.sub.i (x'.sub.i,y'.sub.i) represent the contour point, after second smoothing, of the targeted input contour point P.sub.i, then the coordinates of the contour point after second smoothing are calculated as follows: ##EQU1##
where k.sub.i-1 =k.sub.i+1 =1/4, k.sub.i =1/2.
In FIG. 19, the points P.sub.0, P.sub.1, P.sub.2, P.sub.3 and P.sub.4 are part of a sequence of entered consecutive contour points that have undergone first smoothing, in which the points P.sub.0 and P.sub.4 are corner points and points P.sub.1, P.sub.2 and P.sub.3 are non-corner points. The results of processing at this time are points Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4. Since the points P.sub.0 and P.sub.4 are corner points, the coordinate values thereof become the coordinate values of points Q.sub.0 and Q.sub.4, respectively, without change. The point Q.sub.1 has coordinates calculated from points P.sub.0, P.sub.1, P.sub.2 in accordance with the above-mentioned equation. Similarly, point Q.sub.2 has coordinates calculated from points P.sub.1, P.sub.2, P.sub.3 and point Q.sub.3 has coordinates calculated from points P.sub.2, P.sub.3, P.sub.4 in accordance with the above-mentioned equation.
Such processing is implemented by the CPU 71 as second smoothing of contour data, which has undergone first smoothing, in the prescribed area of RAM 76. The CPU 71 executes this processing loop by loop in order from the first loop to the second, the second loop to the third and so forth, and terminates second smoothing in response to conclusion of this processing with regard to all loops. In the processing of each loop, the CPU 71 executes processing in order from the first point to the second, the second point to the third and so forth. When the processing indicated by Equation (1) is finished for all contour points on the particular loop, the processing of this loop is terminated and processing proceeds to the next loop.
It should be noted that if L-number of contour points reside on one loop, the point preceding the first point is the L-th point and the point following the L-th point is the first point. In the second smoothing set forth above, the contour-point data generated has the same total number of loops as the input contour data that has undergone first smoothing and the same number of contour points in each loop. The CPU 72 outputs the aforementioned results to a separate area of the RAM 76 or to the disk device 72 in the form shown in FIG. 18, thereby concluding the processing for second smoothing (step S3).
Next, the CPU 71 proceeds to step S4, where it transfers the resulting from second smoothing to the binary image reproduction unit 4 via the I/O 75, thus ending the series of processing steps shown in FIG. 16.
The binary image reproduction unit 4 can have the construction of a device described in the specification of Japanese patent application Laid-Open No. 5-20467 already filed by the applicant. On the basis of the contour data subjected to second smoothing and transferred via the I/O, this device is capable of outputting, by raster scanning, a binary image produced by filling in a region demarcated by vectors expressed by the contour data. As described in the specification, this proposed device is realized using binary image output means such as a video printer.
The proposal described in the specification of Japanese Patent Application Laid-Open No. 6-12490 is a further improvement upon the art disclosed in Japanese Patent Application Laid-Open No. 5-174140 and is so adapted that a variable-power image having a low magnification will not become too bloated. More specifically, with the outline extraction unit of Japanese Patent Application Laid-Open No. 5-174140, the boundary exactly midway between a white pixel and a black pixel in an original image is made the object of vector extraction. By contrast, with the art of Japanese Patent Application Laid-Open No. 6-12490, extraction is performed more toward the side of the black pixel (the area of the black pixel narrowed in comparison with the area of the white pixel) and outline smoothing conforming to this extraction is performed.
Meanwhile, methods of reducing the size of an image include the SPC (Selective Processing Conversion) method, the projection method and the PRES method. With the SPC method, slender lines vanish and curves are broken at irregular portions after reduction is performed. The result is a pronounced decline in image quality. Though the projection method provides an improvement in image quality, there is still room for further improvement. The PRES method is a reduction method which applies a fixed magnification of ##EQU2##
both horizontally and vertically, or ##EQU3##
in terms of area ratio. Though a reduced image having excellent image quality is obtained at such magnification, other magnifications cannot be accommodated. The details of the SPC method and projection method are described in "One Study of Facsimile Line-Density Conversion" (Arai, Yasuda), Gazo Denshi Gakkaishi (The Journal of the Institute of Image Electronics Engineers of Japan), Vol. 7, No. 1 (1978), pp. 11.about.18, by way of example. Further, with regard to the PRES method, the details are described in Japanese patent application Laid-Open No. 3-34677.
With the zoom processing for the purpose of enlargement at a comparatively high magnification of 2.times. or more in prior art 1, good results are obtain in terms of high image quality. On the hand, however, the two difficulties mentioned below arise when this art is applied to enlargement at a comparatively low magnification of 1.times. to 2.times. or to zooming for the purpose of size reduction.
First, as described above in connection with FIGS. 11 and 12, a smoothing operation and a zoom operation for enlargement or reduction at a low magnification are performed to define the starting points (contour points) of contour edge vectors (horizontal or vertical vectors) in individual units of the input pixel grid. Frequently, cases arise in which, in the smoothed and zoomed contour points (starting points of horizontal, vertical and diagonal vectors) obtained as a result, the coordinates of a plurality of contour points that are close together before zooming become coordinates at which corresponding positions on the grid of the digital image come to occupy exactly the same position after zooming. In other words, when the pixel grid of a digital image is expressed in a coordinate system based upon whole numbers, the values obtained by executing the smoothing operation (such as calculation of the mid-points of vector edges) and the zoom operation (multiplication by a desired magnification generally expressed by decimals) based upon the coordinates of each contour point extracted from the original image generally are not whole numbers but are numbers involving fractions. However, in order to achieve correspondence to the pixel grid of a digital binary image, it is required that the decimal portions of these numbers be rounded off to obtain integers. When such a conversion to whole numbers is made (as by rounding or discarding fractions), a group of contour points at which coordinate values are whole-number converted to exactly the same coordinate values are produced. A contour vector having starting and end point coordinates that are the same comes to exist on the same contour vector loop. In a set of a plurality of contour vectors (horizontal, vertical or diagonal vectors), the contour vectors contained in the set are connected in regular order as one circuitous loop in which the starting point of one contour vector is the end point of another contour vector without the contour vectors branching or merging. A contour vector whose starting point and end point have the same coordinates is a useless vector, of length zero and indeterminate direction, in terms of expressing a contour represented by a contour vector group to which the vector belongs. Such a contour vector is a cause of malfunction at the time of subsequent reproduction of the binary image. In order to prevent this malfunction, it is necessary to provide extra processing circuitry or processing modules to ascertain the presence of vectors of zero length and to eliminate such vectors if they exist. This leads to higher costs and longer processing time. This tendency is even more pronounced in prior art 2.
The second problem is that an image obtained as the result of zoom processing becomes even more distorted at the time of a size reduction than at the time of low magnification. This will be described based upon an example using FIGS. 4 through 8. FIG. 4 represents an example of a binary image in which the large, shaded circles signify black pixels, with the other pixels being white pixels. Further, x coordinates are plotted along the horizontal axis and y coordinates along the vertical axis. Thus, FIG. 4 expresses a digital binary image in which the seven pixels indicated by coordinates (2,1), (2,2), (3,3), (3,4), (3,5), (4,6), (4,7) are black pixels; all other pixels are white pixels. The ".omicron." and ".DELTA." symbols express coarse-contour edge vectors extracted by the method disclosed in prior art 1. The ".omicron." symbol indicates the starting point of a horizontal vector and the ".DELTA." symbol the starting point of a vertical vector. The extracted coarse-contour vector loop in FIG. 4 is expressed as a point sequence of 12 coarse contour points connected in the order (1.5,0.5)) .fwdarw.(1.5,2.5).fwdarw.(2.5,2.5).fwdarw.(2.5,5.5).fwdarw.(3.5,5. 5).fwdarw.(3.5,7.5).fwdarw.(4.5,7.5).fwdarw.(4.5,5.5).fwdarw.(3.5,5. 5).fwdarw.(3.5,2.5).fwdarw.(2.5,2.5).fwdarw.(2.5,0.5). Of course, the loop may be constructed by making the starting point the coarse contour point (2.5,0.5) expressed as the end of the point sequence and making the end point the coarse contour point (1.5,0.5) expressed as the starting point of the point sequence.
In FIG. 5, the coarse-contour vector loop obtained in the example of FIG. 4 is represented by the dashed lines and a contour vector loop obtained as the result of subjecting the same coarse-contour vector data to the first smoothing of prior art 1 is indicated by the solid lines. The x marks indicate the contour points. In the case of this example, the contour points that have undergone first smoothing are set at the positions of the mid-points of the coarse-contour edge vectors constructing the coarse-contour vector loop.
In FIG. 6, the contour vector loop after first smoothing as shown in FIG. 5 is represented by the dashed lines. The solid lines indicate a contour vector loop obtained by subjecting the coarse-contour vector loop obtained in the example of FIG. 4 to smoothing that includes both the first smoothing and second smoothing, under a condition of 1:1 magnification, by the smoothing method disclosed in prior art 1. The .circleincircle. marks indicate the contour points.
In FIG. 7, the contour vector loop after smoothing as shown in FIG. 6 is represented by the dashed lines. The solid lines indicate a contour vector loop obtained by subjecting the coarse-contour vector loop obtained in the example of FIG. 4 to smoothing and zooming by the smoothing/zoom method of prior art 1 at a zoom ratio (reduction ratio) of 0.7 in the vertical and horizontal directions (namely an area ratio of approximately 0.5). The {character pullout}marks indicate the contour points.
When the thus obtained contour sequence constructing a contour vector loop resulting from the smoothing and zoom processing of prior art 1 is expressed by coordinate values, we have the following in the example depicted in FIG. 7: (1.225,1.05).fwdarw.(1.4,1.8375).fwdarw.(1.75,2.8).fwdarw.(2.1,3. 7625).fwdarw.(2.45,4.55)) .fwdarw.(2.8,5.075).fwdarw.(2.975,4.55).fwdarw.(2.8,3.7625).fwdarw.(2. 45,2.8).fwdarw.(2.1,1.8375).fwdarw.(1.75,1.05).fwdarw.(1.4,0.7). A sequence of coordinate values obtained by rounding off each coordinate value so that the above sequence will approximate the whole-number grid of a digital image is as follows: (1,1).fwdarw.(1,2).fwdarw.(2,3).fwdarw.(2,4).fwdarw.(2,5).fwdarw.(3,5).fwd arw.(3,5).fwdarw.(3,4).fwdarw.(2,3).fwdarw.(2,2).fwdarw.(2,1).fwdarw.(1,1). Thus, contour vectors of length zero having equal starting and end point coordinate values occur, such as at (3,5).fwdarw.(3,5) and at the end point (1,1) and starting point (1,1).
In FIG. 8, the contour vector loop after smoothing and zooming as shown in FIG. 7 is represented by the dashed lines. The solid lines indicate a vector sequence connecting a sequence of coordinate values obtained by subjecting the sequence of contour points constructing the same contour vector loop to a whole-number conversion by rounding off in the manner described above. The whole-number grid positions (the pixels indicated by the whole-number coordinates) inside the area (inclusive of the boundary) delimited by this sequence of coordinate values are expressed as black pixels.
A comparison of FIGS. 4 and 8 shows that FIG. 4 is a black-pixel region comprising seven pixels, while FIG. 8 is the result of subjecting this region to processing at a zoom ratio corresponding to about 0.5.times. in terms of area ratio. FIG. 8 is produced as a black-pixel region comprising nine pixels. The region is thicker and darker.
Thus, in a case where an image represented by outline vectors is subjected to processing for size reduction, vectors having indeterminate direction are produced and the original image cannot be varied in power faithfully.